package com.example.exercises;

/**
 * 264. 丑数 II
 * 给你一个整数 n ，请你找出并返回第 n 个 丑数 。
 * <p>
 * 丑数 就是只包含质因数 2、3 和/或 5 的正整数。
 * <p>
 * 示例 1：
 * 输入：n = 10
 * 输出：12
 * 解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
 * 示例 2：
 * 输入：n = 1
 * 输出：1
 * 解释：1 通常被视为丑数。
 * <p>
 * 思路：与丑数1不同的是：丑数1只是判断某数是否为丑数。而此题是求出第n个丑数。
 * 根据丑数的定义我们得知，它只和2，3，5相关。
 * 我们用还没乘过 2 的最小丑数乘以 2；用还没乘过 3 的最小丑数乘以 3；用还没乘过 5 的最小丑数乘以 5。然后在得到的数字中取最小，就是新的丑数。
 * <p>
 * 实现的方法是用动态规划：
 * 1⃣️我们需要定义 3 个指针 index2, index3, index5 分别表示丑数集合中还没乘过 2，3，5 的丑数位置。
 * 2⃣️然后每次新的丑数 dp[i] = min(dp[index2] * 2, dp[index3] * 3, dp[index5] * 5) 。
 * 3⃣️然后根据 dp[i] 是由 index2, index3, index5 中的哪个相乘得到的，对应的把此 index + 1，表示还没乘过该 index 的最小丑数变大了。
 */
public class UglyNumber2 {
    public static void main(String[] args) {
        UglyNumber2 uglyNumber2 = new UglyNumber2();
        System.out.println(uglyNumber2.nthUglyNumber(4));
    }

    public int nthUglyNumber(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        int p2 = 1, p3 = 1, p5 = 1;
        for (int i = 2; i <= n; i++) {
            int num2 = dp[p2] * 2;
            int num3 = dp[p3] * 3;
            int num5 = dp[p5] * 5;
            dp[i] = Math.min(Math.min(num2, num3), num5);
            if (dp[i] == num2) {
                p2++;
            }
            if (dp[i] == num3) {
                p3++;
            }
            if (dp[i] == num5) {
                p5++;
            }
        }
        return dp[n];
    }
}
